package LearnAlgorithm.c_递归and查找排序;

import java.util.HashMap;

/*
关于加强版水王的题有个想法以扫描一遍数组就解决问题:
水王占总数的一半,说明总数必为偶数;
不失一般性，假设隔一个数就是水王，两两不同最后一定会消减为0
水王可能是最后一个元素，每次扫描的时候，多一个动作，和最后一个元素做比较， 单独计数，计数恰好等于一半
如果不是最后一个元素，即计数不足一半，那么去掉最后一个元素，水王就是留下的那个candidate
 */
public class o乱序数组查找恰好一半的数 {
	public static void main(String[] args) {
		//方法四：不同的数，进行删除
		//O(N)
		int[] arr4 = new int[] {9,7,9,8,9,6,9,4,9,5,9,9};
		scanNotSameDelete(arr4);
	}
	
	public static void scanNotSameDelete(int[] arr) {
		int candidate = arr[0];//定义第一个候选数，这里默认第一个元素是候选数
		int nTimes = 1;//定义候选数出现的次数
		int countOfLast = 0;//定义统计"数组的最后元素"在扫描过程中出现的次数
		for (int i = 1; i < arr.length; i++) {//扫描整个数组
			if (arr[arr.length - 1] == arr[i]) {//每一次循环都进行比较
				countOfLast++;
			}
			if (nTimes == 0) {//如果次数==零
				candidate = arr[i];//新的元素作为候选数
				nTimes = 1;//重置为1
				continue;//跳出这次循环
			}
			if (candidate == arr[i]) {//如果新的元素==candidate
				nTimes++;//次数+1
			} else {
				nTimes--;//否则-1
			}
		}
		if (countOfLast == (arr.length >>> 1)) {//正好等于一半的情况，最后的需要加一个判断，根据countOfLast的情况判断
			System.out.println(arr[arr.length - 1]);//返回最后一个元素
		} else {
			System.out.println(candidate);//返回跳出循环时的那个candidate
		}
	}
}